{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Julia's Type System"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia programs manipulate *values*, and every value has two parts: a *type* part and a data part. The type part answers the question \"what kind of thing is this?\", and the data part distinguishes one thing of a certain kind from every other thing of that kind."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1. DataType"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case the type is `Int64` and the data part is the bits `...0011`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Julia types are also values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(Int64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(DataType)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, the identity `typeof(typeof(x)) === DataType` holds for all values in Julia. `DataType` is the backbone of the entire system. It does many jobs, which can be identified by looking inside a `DataType` object:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### DataType Job 1: A symbolic description"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This consists of a name (which is mostly a string), and a vector of sub-components:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = typeof(1+2im)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### DataType Job 2: A nominal hierarchy of types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DataTypes form a tree of declared type relationships (\"an x is-a y\"):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.super"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.super.super.super.super  # `Any` is the built-in top of the hierarchy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### DataType Job 3: Describe the representation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.name.names"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.mutable   # whether this was declared with `type` (vs. `immutable`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.abstract  # whether this was declared with `abstract`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.ninitialized"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T.layout"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining struct types\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "struct Point\n",
    "    x::Float64\n",
    "    y::Float64\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Point(1,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Abstract vs. Concrete"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`abstract` types can have declared subtypes, while concrete types can have instances. These are separated because if an `X` IS-A `Y`, and `Y` specifies a representation, then `X` had better have the same representation.\n",
    "\n",
    "\"car is-a vehicle\" is correct because \"vehicle\" is an abstract concept that doesn't commit to any specifics. But if I tell you I'm giving you a Porsche, it needs to look like a Porsche."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A type `T` is concrete if there could be some value `x` such that `typeof(x) === T`. This is also sometimes called a \"leaf type\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "abstract type PointLike end\n",
    "\n",
    "# struct Point <: PointLike"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2. Type parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Type parameters can be completely or partially specified:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Array{Int}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[1] isa Array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Array{Int,2}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A type is concrete (can have instances) if\n",
    "    1. it is not declared `abstract`\n",
    "    2. all parameters are specified"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[1] isa Array{Int,1}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[1] isa Array{Int}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[1] isa Array{Number}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Int <: Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Types with different *specified* parameters are just different, and have no subtype relationship. This is called *invariance*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining types with parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "struct GenericPoint{T<:Real}\n",
    "    x::T\n",
    "    y::T\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GenericPoint(1,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GenericPoint(1.0,2.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GenericPoint(1,2.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tuple types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof((1,2.0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Very similar to other DataTypes, except\n",
    "    1. Have no field names, only indices\n",
    "    2. `T.parameters == T.types`\n",
    "    3. Are always immutable\n",
    "    4. Can have any number of fields"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These factors conspire to make Tuples the only *covariant* types in Julia:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Tuple{Int} <: Tuple{Number}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Tuple type is concrete iff all its field types are."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tuple types can be abstract with respect to the number of elements. These are called variadic tuple types, or vararg types."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Tuple{Int,Vararg{Int}}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that `Vararg` refers to the tail of a tuple type, and as such is not a first-class type itself. It only makes sense inside a Tuple type. This is a bit unfortunate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second parameter to `Vararg` is a length, which can also be either unspecified (as above), or specified:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Tuple{Int,Vararg{Int,2}}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 3. Larger type domains"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Union types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A type can be thought of as a set of possible values. A type expresses *uncertainty* about which value we have. You can do set operations on them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Union{Int64,Float64}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1 isa Union{Int64,Float64}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Int64 <: Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Int64 <: Union{Int64,Float64}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Union{Int,String} <: Union{Int,String,Float32}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeintersect(Union{Int,String}, Union{Int,String,Float32})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Union types naturally lend themselves to missing data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = [1.1, missing, 3.2, missing, 5.7, 0.4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### UnionAll types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an *iterated union* of types.\n",
    "\n",
    "`Array{T,1} where T<:Integer`\n",
    "\n",
    "Means \"the union of all types of the form Array{T,1} where T is a subtype of Integer\".\n",
    "\n",
    "This expresses uncertainty about the value of a parameter.\n",
    "\n",
    "This concept exists in all versions of Julia, but does not have syntax or fully correct support within the system until upcoming v0.6.0 (currently on branch jb/subtype).\n",
    "\n",
    "* Since this kind of type introduces *variables*, its expressive power is (probably) equivalent to quantified boolean formulas.\n",
    "* Requires a quantified-SAT solver in the compiler.\n",
    "* Under common assumptions, harder than NP-complete."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# this definition is in the Base library\n",
    "Vector = Array{T,1} where T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are used to express \"unspecified parameters\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These also describe methods with \"method parameters\" (or \"static parameters\"):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "func(a::Array{T,1}) where {T<:Integer} = T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "func([0x00])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "func([1.0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Question\n",
    "\n",
    "What is the difference between\n",
    "\n",
    "`Vector{Vector{T}} where T`\n",
    "\n",
    "and\n",
    "\n",
    "`Vector{Vector{T} where T}`?\n",
    "\n",
    "Is one a subtype of the other?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Define a `UnitPoint{<:Real}` parametric struct type which has `x` and `y` fields of type `T` and which has an inner constructor that normalizes its arguments by diving them by `hypot(x, y)` upon construction, guaranteeing that the resulting point is on the unit circle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Julia 1.1.0-DEV",
   "language": "julia",
   "name": "julia-1.1"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.1.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
